package algorithm.排序法;

/**
 *选择排序法在效率上比插入法高，虽然比较的操作次数相同，但是交换的次数少于插入法
 * @author Jun
 */
public class sort {
    /**
     * 插入排序法
     * @param arr
     */
    public static void insertionSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int key=arr[i];
            int position = i;
            while(position>0&&key>arr[position-1]){
                arr[position]=arr[position-1];
                position--;
            }
            arr[position]=key;
        }
        for (int a:arr){
            System.out.println(a);
        }
    }
    /**
     * 选择排序法，每次j循环都将最小的数字放到指当前i位置
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int temp = 0;
        int min ;
        for (int i = 0; i < arr.length - 1; i++) {
            min=i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] < arr[j]) {
                    min = j;
                }
            }
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
        }
        for(int a:arr){
            System.out.println(a);
        }
    }

    /**
     * 冒泡排序法
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int a : arr) {
            System.out.println(a);
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 2, 3, 6, 5, 7, 4, 10, 1};
//        selectSort(arr);
//        System.out.println("——————————————————————————————————————————————————————");
//        bubbleSort(arr);
//        System.out.println("——————————————————————————————————————————————————————");
        insertionSort(arr);
    }
}
